「CSP-S 2024」 染色

这道题我不知道昨年的自己是多蒻才完全没有思路┏┛墓┗┓...(((m-__-)m

首先我们易得，如果我们要得到某两点对应的贡献，可以很迅速的想到要把这两点之间的所有点涂色为相同的才行

即要使$color[i] == color[j]$，需要$color[i+1~j-1]=!color[i]$，此时带来的贡献是$val[i]$

所以操作就转化为了将一段区间的贡献推平换贡献的过程，而被推平段里面的所有贡献全部清除

所以我们可以记录每一个相同数他们对应的区间(不用解释我们也知道选择最近的那个点更优)

然后线性$DP$实现上述的"换贡献"的过程就行了

实现上要注意一个细节，因为我们没有考虑相邻的相同权值的点，而无论如何这些点的贡献一定可以被计

所以可以预处理区间时不记录这些相邻的区间，而是直接加上他们的贡献

/*
易得如果我们要使 color[i] == color[j], 需要 color[i+1~j-1]=!color[i], 此时带来的贡献是 val[i]
所以记录每个颜色的上一个相同颜色, DP 时就时考虑将一段推平尝试新贡献的过程 
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair< int,int >
#define QWQ return 0;
#define reg register

const int N=1e6+10;

int lst[N], to[N], val[N];
ll f[N];

void sovel()
{
    //多测不清空，_____
    memset( lst,0,sizeof( lst ) );
    memset( to,0,sizeof( to ) );
    memset( val,0,sizeof( val ) );
    memset( f,0,sizeof( f ) ); 
    int n;
    cin>>n;
    ll ans=0;
    for( reg int i=1;i<=n;i++ )
    {
        int x;
        cin>>x;
        if( lst[x] )
        {
            if( lst[x] == i-1 )
                ans+=x;
            else
            {
                to[i-1]=lst[x]+1;
                val[i-1]=x;
                //即推平 lst[x]+1~i-1 这一段所带来的贡献是 x 
            }
        }
        lst[x]=i;
    } 
    for( reg int i=1;i<=n;i++ )
    {
        f[i]=f[i-1]; 
        if( to[i] ) f[i]=max( f[i],f[to[i]-1]+val[i] );//只有前面有相同的数推平尝试才有意义 
    }
    ans+=f[n];
    cout<<ans<<"\n";
}

int main()
{
    freopen( "color.in","r",stdin );
    freopen( "color.out","w",stdout );
    ios::sync_with_stdio( false );
    cin.tie( nullptr ), cout.tie( nullptr );
    reg int t;
    for( cin>>t;t;t-- )
        sovel();
    QWQ
}